package class20;

/**
 * @author YZY
 * @since 2022/8/20 13:26
 * <a href="https://leetcode.cn/problems/longest-palindromic-subsequence/">516. 最长回文子序列</a>
 * 方法一：样本对应模型，可以尝试用 最长公共子序列 那道题的解法，只需要将字符串反转一下，当成str2，就是一个 最长公共子序列 的问题
 */
public class Code01_PalindromeSubsequence1 {

    // 暴力递归
    public static int longestPalindromeSubseq1(String s) {
        char[] str1 = s.toCharArray();
        char[] str2 = new char[str1.length];
        for (int i = 0; i < str1.length; ++i) {
            str2[i] = str1[str1.length - 1 - i];
        }
        return process1(str1, str2, 0, 0);
    }

    private static int process1(char[] str1, char[] str2, int i1, int i2) {
        if (i1 == str1.length - 1 && i2 == str2.length - 1) {
            return str1[i1] == str2[i2] ? 1 : 0;
        }
        if (i1 == str1.length - 1) {
            return str1[i1] == str2[i2] ? 1 : process1(str1, str2, i1, i2 + 1);
        }
        if (i2 == str2.length - 1) {
            return str1[i1] == str2[i2] ? 1 : process1(str1, str2, i1 + 1, i2);
        }
        // i1 != str1.length - 1 && i2 != str2.length - 1
        int case1 = process1(str1, str2, i1 + 1, i2);
        int case2 = process1(str1, str2, i1, i2 + 1);
        int case3 = str1[i1] == str2[i2] ? 1 + process1(str1, str2, i1 + 1, i2 + 1) : 0;
        return Math.max(case3, Math.max(case1, case2));
    }

    // 记忆化搜索
    public static int longestPalindromeSubseq2(String s) {
        char[] str1 = s.toCharArray();
        char[] str2 = new char[str1.length];
        for (int i = 0; i < str1.length; ++i) {
            str2[i] = str1[str1.length - 1 - i];
        }
        int[][] dp = new int[str1.length][str2.length];
        return process2(str1, str2, 0, 0, dp);
    }

    private static int process2(char[] str1, char[] str2, int i1, int i2, int[][] dp) {
        if (dp[i1][i2] != 0) {
            return dp[i1][i2];
        }
        if (i1 == str1.length - 1 && i2 == str2.length - 1) {
            return str1[i1] == str2[i2] ? 1 : 0;
        }
        if (i1 == str1.length - 1) {
            return str1[i1] == str2[i2] ? 1 : process2(str1, str2, i1, i2 + 1, dp);
        }
        if (i2 == str2.length - 1) {
            return str1[i1] == str2[i2] ? 1 : process2(str1, str2, i1 + 1, i2, dp);
        }
        // i1 != str1.length - 1 && i2 != str2.length - 1
        int case1 = process2(str1, str2, i1 + 1, i2, dp);
        int case2 = process2(str1, str2, i1, i2 + 1, dp);
        int case3 = str1[i1] == str2[i2] ? 1 + process2(str1, str2, i1 + 1, i2 + 1, dp) : 0;
        return dp[i1][i2] = Math.max(case3, Math.max(case1, case2));
    }

    // 动态规划
    public static int longestPalindromeSubseq3(String s) {
        char[] str1 = s.toCharArray();
        char[] str2 = new char[str1.length];
        int len1 = str1.length;
        int len2 = str2.length;
        for (int i = 0; i < str1.length; ++i) {
            str2[i] = str1[len1 - 1 - i];
        }
        int[][] dp = new int[len1][len2];
        dp[len1 - 1][len2 - 1] = str1[len1 - 1] == str2[len2 - 1] ? 1 : 0;
        for (int i2 = len2 - 1 - 1; i2 >= 0; --i2) {
            dp[len1 - 1][i2] = str1[len1 - 1] == str2[i2] ? 1 : dp[len1 - 1][i2 + 1];
        }
        for (int i1 = len1 - 1 - 1; i1 >= 0; --i1) {
            dp[i1][len2 - 1] = str1[i1] == str2[len2 - 1] ? 1 : dp[i1 + 1][len2 - 1];
        }
        for (int i1 = len1 - 1 - 1; i1 >= 0; --i1) {
            for (int i2 = len2 - 1 - 1; i2 >= 0; --i2) {
                int case1 = dp[i1 + 1][i2];
                int case2 = dp[i1][i2 + 1];
                int case3 = str1[i1] == str2[i2] ? 1 + dp[i1 + 1][i2 + 1] : 0;
                dp[i1][i2] = Math.max(case3, Math.max(case1, case2));
            }
        }
        return dp[0][0];
    }

}
